//============================================================================
// Name        : 7_1_Linux.cpp
// Author      : Eric Chen
// Version     : alpha
// Copyright   : Your copyright notice
// Description : Hoare partition correctness, Ansi-style
//============================================================================

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int SimapleArray[]={13,19,9,5,12,8,7,4,11,2,6,21};
class PrintInt
{
	public:
		void operator()(int elem) const
		{
			cout << elem<<' ';
		}
};

//i starts from one
int hoare_partition(vector<int>& vec,int p, int r)
{
	int x=vec[p-1];
	int i=p;
	int j=r;
	for(;true;)
	{
		for(;vec[j-1]>x;--j){}
		for(;vec[i-1]<x;++i){}
		if(i<j)
			swap(vec[i-1],vec[j-1]);
		else
			return j;

	}
}

void quick_sort(vector<int> &vec,int p, int r)
{
	if(p<r)
	{
		int q=hoare_partition(vec,p,r);
		quick_sort(vec,p,q-1);
		quick_sort(vec,q+1,r);
	}
}

int main()
{
	vector<int> A;
	int size=sizeof(SimapleArray)/sizeof(int);
	for(int i=0;i<size;i++)
	{
		A.push_back(SimapleArray[i]);
	}
	cout << "Array before sorting\n";
	for_each(A.begin(), A.end(), PrintInt());
	cout<<endl;
	cout << "Quick sorts the array"<<endl;
	quick_sort(A,1,size);
	cout << "Array after sorting\n";
	for_each(A.begin(), A.end(), PrintInt());
	cout<<endl;
	return 0;
}
